package com.salim.leetcode.$45;

public class JumpGameII {
    private static int[] array;
    private static int[] jumped;
    public int jump(int[] nums) {
        array = nums;
        if(nums.length<=1){
            return 0;
        }
        jumped = new int[nums.length];
        doJump(0,0);
        return jumped[nums.length-1];
    }

    public void doJump(int index,int lastCount){
        for(int i=array[index];i>0;i--){
            if(array.length-1>index+i){
                if(jumped[index + i]==0||lastCount+1<jumped[index + i]){
                    jumped[index+i] = lastCount+1;
                    doJump(index+i,lastCount+1);
                }else{
                    break;
                }
            }else if(array.length-1<=index+i){
                if(jumped[array.length-1]==0||lastCount+1<jumped[array.length-1]){
                    jumped[array.length-1] = lastCount+1;
                    break;
                }else{
                    break;
                }
            }
        }
    }
}
